package com.shuzijun.leetcode.editor.cn;

import java.util.ArrayList;
import java.util.List;

public class CombinationSum{
    public static void main(String[] args) {
         
         Solution solution = new CombinationSum().new Solution();
        
        
    }
    //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
        private ArrayList<List<Integer>> result = new ArrayList<>();
    public List<List<Integer>> combinationSum(int[] candidates, int target) {

        backTtack(candidates,0,target,new ArrayList<>());
        return result;
    }

        private void backTtack(int[] candidates, int k, int left, ArrayList<Object> path) {
            if (left == 0){
                result.add(new ArrayList(path));
                return;
            }

            if (k == candidates.length){
                return;
            }

            for (int i = 0; i <= left/candidates[k]; i++) {
                for (int j = 0; j < i; j++) {
                    path.add(candidates[k]);
                }
                backTtack(candidates,k+1,left-i*candidates[k],path);
                for (int j = 0; j < i; j++) {
                    path.remove(path.size()-1);
                }
            }
        }

    }
//leetcode submit region end(Prohibit modification and deletion)

}